{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Railway dispatching\n",
    "Public transport is an industry with many use cases that benefit from mathematical optimization. Examples include long-term planning (which services to operate at what frequency, timetabling of services), mid-term (assigning rolling stock and crew to train trips) and short-term (rescheduling, dispatching). In this notebook we consider the railway dispatching problem. We are given a set of trains with their current position and desired route. The challenge is to decide on the sequence of movements, so each train reaches its endpoint as soon as possible while respecting capacity limitations at the tracks and intermediate stations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Load required packages\n",
    "If you have a Gurobi license and installed the software already, you can skip the installation of `gurobipy`, but always make sure you have the [latest version](https://www.gurobi.com/downloads/gurobi-software) available."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy pandas plotly.express nbformat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools as it\n",
    "import math\n",
    "import pandas as pd\n",
    "import plotly.express as px\n",
    "import datetime as dt\n",
    "from os import path\n",
    "import gurobipy as gp\n",
    "from gurobipy import GRB"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Retrieving the data\n",
    "We will be loading our scenarios from CSV files. These can be found in the `data` folder; each scenario consists of various CSV files within a subfolder. The files contain the following data:\n",
    "- `stations.csv` contains the railway stations. Each has a `capacity` (number of trains that can be at the station concurrently) and `duration` (time required for a stop at the station). Stations also have a `y` coordinate for visualizing the schedule later.\n",
    "- `tracks.csv` contains the railway tracks that connect pairs of stations. Each has a `capacity` and `duration` as above, as well as a `start` and `end` station. We assume tracks can be traversed in both directions, so the order of `start` and `end` is not relevant.\n",
    "- `routes.csv` contains predefined routes through the network. Each route is a list of resources (stations and tracks).\n",
    "- `trains.csv` contains the trains that require scheduling for traversing the network. Each train follows a `route`, but may `start` at any point in the route."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = 'linear'\n",
    "folder = f'data/{dataset}'\n",
    "df_stations = pd.read_csv(path.join(folder, 'stations.csv')).set_index('id')\n",
    "df_tracks = pd.read_csv(path.join(folder, 'tracks.csv')).set_index('id')\n",
    "df_routes = pd.read_csv(path.join(folder, 'routes.csv')).set_index('id')\n",
    "df_trains = pd.read_csv(path.join(folder, 'trains.csv')).set_index('id')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will do a bit of processing, to make it easier to use our data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# For each route, parse the station/track string\n",
    "routes = df_routes['resources'].map(lambda route: [int(res) for res in route.split('-')]).to_dict()\n",
    "\n",
    "# For each train, find the corresponding route and apply the starting position\n",
    "trains = df_trains.apply(lambda row: list(it.dropwhile(lambda resource: resource!=row.start, routes[row.route])), axis=1).to_dict()\n",
    "\n",
    "# For each resource, find the duration and capacity\n",
    "duration = pd.concat([df_tracks['duration'], df_stations['duration']]).to_dict()\n",
    "capacity = pd.concat([df_tracks['capacity'], df_stations['capacity']]).to_dict()\n",
    "\n",
    "# Find Y coordinates for the stations\n",
    "station_y = df_stations['y'].to_dict()\n",
    "\n",
    "# For each track, find the pair of stations on both sides of the track\n",
    "track_stations = df_tracks.apply(lambda track: (track.start, track.end), axis=1)\n",
    "\n",
    "# Find the set of resources with their types (S=station, T=track)\n",
    "resource_type = { key: 'S' for key in df_stations.index } | { key: 'T' for key in df_tracks.index }\n",
    "resources = resource_type.keys()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can show the input data as a simple Dataframe combining tracks and stations as below. Note that tracks don't have `y` values while stations don't have `endpoints` values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>type</th>\n",
       "      <th>duration</th>\n",
       "      <th>capacity</th>\n",
       "      <th>y</th>\n",
       "      <th>endpoints</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>S</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>0.0</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>T</td>\n",
       "      <td>6</td>\n",
       "      <td>1</td>\n",
       "      <td>NaN</td>\n",
       "      <td>(0, 2)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>S</td>\n",
       "      <td>4</td>\n",
       "      <td>2</td>\n",
       "      <td>6.0</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>T</td>\n",
       "      <td>8</td>\n",
       "      <td>1</td>\n",
       "      <td>NaN</td>\n",
       "      <td>(2, 4)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>S</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>14.0</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>T</td>\n",
       "      <td>5</td>\n",
       "      <td>1</td>\n",
       "      <td>NaN</td>\n",
       "      <td>(4, 6)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>S</td>\n",
       "      <td>2</td>\n",
       "      <td>2</td>\n",
       "      <td>19.0</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  type  duration  capacity     y endpoints\n",
       "0    S         2         2   0.0       NaN\n",
       "1    T         6         1   NaN    (0, 2)\n",
       "2    S         4         2   6.0       NaN\n",
       "3    T         8         1   NaN    (2, 4)\n",
       "4    S         2         2  14.0       NaN\n",
       "5    T         5         1   NaN    (4, 6)\n",
       "6    S         2         2  19.0       NaN"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pd.DataFrame({'type': resource_type, 'duration': duration, 'capacity': capacity, 'y': station_y, 'endpoints': track_stations})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To make our lives easier, we will define a little helper function that gives us, for a particular train and resource, the resource immediately *after* the given resource along the route for that train. If the given resource is the last one in the route, then we will return `None`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_next_resource(train, resource):\n",
    "    route = trains[train]\n",
    "    index = route.index(resource)\n",
    "    return route[index + 1] if index < len(route)-1 else None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The various datasets included with this notebook are illustrated below. Nodes (circles) indicate stations whereas lines represent tracks. While the `linear` model does not involve branching, the `yshape` is a bit more complex and the `xshape` adds even more complexity.\n",
    "\n",
    "![](images/Slide2.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mathematical optimization model\n",
    "\n",
    "### Timing aspects\n",
    "The main decision in this use case is about timing: when should each train visit each resource.\n",
    "\n",
    "Let's define a few important sets.\n",
    "- Let $R$ the set of resources; these include both stations and tracks.\n",
    "- Let $I$ be the set of trains; we define $R_i$ to be the (ordered) set of resources to be visited by train $i \\in I$\n",
    "\n",
    "For timing, we introduce two sets of decision variables.\n",
    "- The main variables will be $t_{i,r}$ to denote the time by which train $i$ visits (starts occupying) resource $r$.\n",
    "- Since we want to look at total throughput time, we will also define $t^F_i \\: \\forall i \\in I$ as the finish time for train $i$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Set parameter LicenseID to value 692374\n"
     ]
    }
   ],
   "source": [
    "model = gp.Model()\n",
    "events = gp.tuplelist([(train, resource) for train, route in trains.items() for resource in route])\n",
    "t = model.addVars(events, name='t')\n",
    "tf = model.addVars(trains.keys(), name='tf')\n",
    "\n",
    "# Helper function to retrieve 't' or 'tf', depending on if resource=None\n",
    "def tvar(train, resource):\n",
    "    return t[train, resource] if resource is not None else tf[train]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we consider a single train, we know that resources are visited in a particular order and the train will take a known duration to visit each resource.\n",
    "- Let's assume $dur_r$ for each resource $r \\in R$ denotes the duration required for traversing the resource\n",
    "- Then for a pair of resources $(r, r')$ visited consecutively by a train $i$, we know $t_{i,r'} = t_{i,r} + dur_r$\n",
    "\n",
    "So we can link pairs of consecutive time variables for each train using that equation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Precedence constraints\n",
    "for train, route in trains.items():\n",
    "    for train_i in range(len(route)-1):\n",
    "        # We assume that trains are present in the network from the start, so must\n",
    "        # have their first event equal to 0.\n",
    "        if train_i==0:\n",
    "            model.addConstr(t[train, route[train_i+1]] - t[train, route[train_i]] >= duration[route[train_i]])\n",
    "        else:\n",
    "            model.addConstr(t[train, route[train_i+1]] - t[train, route[train_i]] >= duration[route[train_i]])            \n",
    "    model.addConstr(tf[train] - t[train, route[len(route)-1]] == duration[route[len(route)-1]])\n",
    "\n",
    "# Starting position\n",
    "for train in trains:\n",
    "    resource = trains[train][0]\n",
    "    t[train, resource].UB=0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conflict detection\n",
    "If we would solve the model as it is now, we would optimize each train separately since there are no constraints linking them together. The relationship between trains is introduced because they share certain resources with limited capacity.\n",
    "\n",
    "In order to deal with resource capacity, the first step is to focus on pairs of trains $i$ and $j$ that share a particular resource $r$. Let's assume train $i$ visits resource $u$ after $r$, while train $j$ visits resource $v$ next. \n",
    "\n",
    "Now depending on the value of the $t$ variables, we will face one of three situations:\n",
    "- Train $i$ precedes $j$, which would mean train $i$ reaches $u$ before train $j$ reaches $r$.\n",
    "- Similarly, train $j$ might precede train $i$ when it reaches $v$ before train $i$ reaches $r$.\n",
    "- Finally, trains $i$ and $j$ might be sharing the resource concurrently for some period of time.\n",
    "\n",
    " We can introduce binary variables to represent each of the three scenarios above:\n",
    "- $y_{i,j,r}=1$ when $i$ precedes $j$; for this we add constraint $t_{j,r} - t_{i,u} \\geq -M \\cdot (1-y_{i,j,r})$\n",
    "- $y_{j,i,r}=1$ when $j$ precedes $i$; for this we add constraint $t_{i,r} - t_{j,v} \\geq -M \\cdot (1-y_{j,i,r})$\n",
    "- $x_{i,j,r}=1$ when $i$ and $j$ meet at resource $r$; for this we have a pair of constraints $t_{j,v} - t_{i,r} \\geq -M \\cdot (1-x_{i,j,r})$ and $t_{i,u} - t_{j,r} \\geq -M \\cdot (1-x_{i,j,r})$\n",
    "- By definition, we must have $y_{i,j,r} + y_{j,i,r} + x_{i,j,r} = 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](images/Slide1.png)\n",
    "\n",
    "The left diagram shows how two trains $i$ and $i'$ visit a shared resource $r$ and then continue to resource $u$ resp. $v$. The right diagram shows the various events involved in conflict detection at resource $r$. Each arrow indicates that the head node must follow the tail node. The $P$ arrows indicate precedence constraints for a single train. The $X$ constraints apply when the trains occupy the resource simultaneously. The $Y$ arrows apply when one train precedes the other one on the resource $r$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = sum(duration) * len(trains)\n",
    "\n",
    "def create_disjunct_constraints(resource, train_i, resource_u, train_j, resource_v, M):\n",
    "    t_ir = tvar(train_i, resource)\n",
    "    t_iu = tvar(train_i, resource_u)\n",
    "    t_jr = tvar(train_j, resource)\n",
    "    t_jv = tvar(train_j, resource_v)\n",
    "\n",
    "    # A before B\n",
    "    y_ab = model.addVar(vtype=GRB.BINARY, name=f'y[{resource},{train_i},{train_j}]')\n",
    "    model.addConstr(t_jr - t_iu >= -M *(1-y_ab), name=f'y[{resource},{train_i},{train_j}]')\n",
    "\n",
    "    # B before A\n",
    "    y_ba = model.addVar(vtype=GRB.BINARY, name=f'y[{resource},{train_j},{train_i}]')\n",
    "    model.addConstr(t_ir - t_jv >= -M *(1-y_ba), name=f'y[{resource},{train_j},{train_i}]')\n",
    "\n",
    "    # A and B meet\n",
    "    x = model.addVar(vtype=GRB.BINARY, name=f'x[{resource},{train_i},{train_j}]')\n",
    "    model.addConstr(t_jv - t_ir >= -M *(1-x), name=f'x1[{resource},{train_i},{train_j}]')\n",
    "    model.addConstr(t_iu - t_jr >= -M *(1-x), name=f'x2[{resource},{train_i},{train_j}]')\n",
    "\n",
    "    # Have exactly one of three situations\n",
    "    model.addConstr(y_ab + y_ba + x == 1, name=f'xy[{resource},{train_i},{train_j}]')\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Resource capacity\n",
    "With the constraints above, we would only derive the correct values for $x$ and $y$ given the values of $t$, without impacting the feasible region for $t$. The missing piece is the limited capacity of our resources.\n",
    "\n",
    "Let's assume we have a resource with capacity $c$, which is visited by $n$ trains. If $c \\geq n$ then we don't need to do anything. Otherwise, we will need constraints to ensure we never have more than $c$ resources at the same time. How can we model this using the $x$ variables for pairs of trains?\n",
    "\n",
    "Imagine we have $c+1$ trains visiting at the same time. Those trains would form ${c+1 \\choose 2}$ pairs of trains $(i,j)$ and all corresponding variables $y_{i,j,r}$ would have value 1 since they all meet at the same time. The sum of those variables would therefore equal ${c+1 \\choose 2}$.\n",
    "\n",
    "So the way to prevent this, is by adding a constraint for every subset of $c+1$ trains. That constraint should guarantee that at least one pair of trains in the subset does not meet at the resource. In other words, the sum of $y$ variables in the subset would need to be less than ${c+1 \\choose 2}$.\n",
    "\n",
    "The algorithm to generate those constraints is as follows:\n",
    "- Iterate over all resources\n",
    "- Find all pairs of trains visiting the resource\n",
    "- Generate the $x$ and $y$ variables using the helper function above, for each pair of trains\n",
    "- If the number of trains does not exceed $c$, then skip\n",
    "- Else, if the resource has capacity $c>1$:\n",
    "  - Generate all subsets of trains of size $c+1$\n",
    "  - Add a constraint that ensures the sum of $y$ variables for pairs of trains in this subset, does not exceed ${c+1 \\choose 2}$\n",
    "- Otherwise, we can simply force $x=0$ to prevent overlap."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Conflicts\n",
    "for resource in resources:\n",
    "    # Find trains that visit\n",
    "    resource_events = events.select('*', resource)\n",
    "    resource_trains = [t for (t,r) in resource_events]\n",
    "    trains_with_next = []\n",
    "\n",
    "    # For each train, find the consecutive event\n",
    "    for train in resource_trains:\n",
    "        next_resource = get_next_resource(train, resource)\n",
    "        trains_with_next.append((train, next_resource))\n",
    "\n",
    "    # List of X variables to use for hotspot constraint later\n",
    "    xlist = {}\n",
    "\n",
    "    # Consider pairs of trains\n",
    "    pairs = it.combinations(trains_with_next, 2)\n",
    "    for pair in pairs:\n",
    "        ((train_i, resource_u), (train_j, resource_v)) = pair\n",
    "        xlist[train_i,train_j] = create_disjunct_constraints(resource, train_i, resource_u, train_j, resource_v, M)\n",
    "\n",
    "    # Add hotspot constraints\n",
    "    if len(resource_trains) <= capacity[resource]:\n",
    "        continue\n",
    "    elif(capacity[resource] > 1):\n",
    "        subsets = it.combinations(resource_trains, capacity[resource]+1)\n",
    "        rhs = math.comb(capacity[resource]+1, 2) - 1\n",
    "        for subset in subsets:\n",
    "            pairs = it.combinations(subset, 2)\n",
    "            xsel = [xlist[ta,tb] for (ta,tb) in pairs]\n",
    "            suffix = ','.join(list(subset))\n",
    "            model.addConstr(gp.quicksum(xsel) <= rhs, f'h[{resource},{suffix}]')            \n",
    "    else:\n",
    "        for x in xlist.values():\n",
    "            x.UB = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Additional complexity\n",
    "If desired, you can add more complexity to the model here by adding constraints on the event timing. For example, in the `linear` dataset you might want to force train `F` to arrive before train `E`. We can do that by uncommenting the statement below. Note how this increases overall delay, since train `E` must wait for train `F` at a station."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "#model.addConstr(tf['F'] <= tf['E'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Minimizing delays\n",
    "And that's most of the work! We have defined timing variables with precedence constraints per train; then we added relationships between trains when they share resources and made sure those trains never exceed the resource capacity. Now the only missing piece is an objective function. To optimize passenger experience as well as operational efficiency, we want to get all trains to their endpoint as soon as possible. We could model this in several ways:\n",
    "- One simple objective could be to simply sum up the arrival times at the endpoints. Here it doesn't matter whether one train has a long delay, or the same total delay is distributed over multiple trains. What we do achieve here, is that resources with limited capacity are being used as soon as possible.\n",
    "- Another objective could be to minimize the time by which *all* trains have arrived at their endpoint. This would be similar to the concept of *makespan* in other scheduling problems.\n",
    "- These values are being determined not only by our dispatching decisions, but also by the minimum travel time for each train which cannot be avoided. We could compensate for that by subtracting this minimum duration from the scheduled arrival time of each train. Note that since we're just subtracting a constant value, we will get the same optimal solution as the previous bullet.\n",
    "- Finally, to make things more interesting, we could try and distribute delay between trains. While this might have negative impact on operational efficiency (it could be easier handling a single delay, than many small delays), it does represent a concept that could be considered *fairness*.\n",
    "\n",
    "Below we will take the third approach, but one can easily modify the objective function to work with any of the ideas mentioned here. The fourth approach requires a full Gurobi license as it involves a quadratic objective."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delay(train):\n",
    "    min_duration = sum(duration[resource] for resource in trains[train])\n",
    "    return tf[train] - min_duration\n",
    "    \n",
    "model.setObjective(gp.quicksum(delay(train) for train in trains))\n",
    "model.ModelSense = GRB.MINIMIZE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solving the model\n",
    "Now we're ready to solve the model. Gurobi does this within a couple of seconds:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 12.0.0 build v12.0.0rc1 (mac64[arm] - Darwin 24.1.0 24B91)\n",
      "\n",
      "CPU model: Apple M1\n",
      "Thread count: 8 physical cores, 8 logical processors, using up to 8 threads\n",
      "\n",
      "Optimize a model with 367 rows, 218 columns and 1069 nonzeros\n",
      "Model fingerprint: 0x55c46576\n",
      "Variable types: 38 continuous, 180 integer (180 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+02]\n",
      "  Objective range  [1e+00, 1e+00]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 1e+02]\n",
      "Presolve removed 154 rows and 108 columns\n",
      "Presolve time: 0.00s\n",
      "Presolved: 213 rows, 110 columns, 641 nonzeros\n",
      "Variable types: 26 continuous, 84 integer (84 binary)\n",
      "Found heuristic solution: objective 70.0000000\n",
      "\n",
      "Root relaxation: objective 1.000000e+01, 39 iterations, 0.00 seconds (0.00 work units)\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0   10.00000    0    9   70.00000   10.00000  85.7%     -    0s\n",
      "H    0     0                      67.0000000   10.00000  85.1%     -    0s\n",
      "H    0     0                      54.0000000   10.00000  81.5%     -    0s\n",
      "H    0     0                      49.0000000   10.00000  79.6%     -    0s\n",
      "     0     0   24.80544    0   19   49.00000   24.80544  49.4%     -    0s\n",
      "     0     0   26.90349    0   19   49.00000   26.90349  45.1%     -    0s\n",
      "     0     0   29.48228    0   20   49.00000   29.48228  39.8%     -    0s\n",
      "     0     0   30.44468    0   20   49.00000   30.44468  37.9%     -    0s\n",
      "     0     0   30.65423    0   16   49.00000   30.65423  37.4%     -    0s\n",
      "     0     0   30.65531    0   16   49.00000   30.65531  37.4%     -    0s\n",
      "     0     0   33.98537    0   20   49.00000   33.98537  30.6%     -    0s\n",
      "     0     0   34.08360    0   20   49.00000   34.08360  30.4%     -    0s\n",
      "H    0     0                      47.0000000   34.08360  27.5%     -    0s\n",
      "     0     0   35.05769    0    9   47.00000   35.05769  25.4%     -    0s\n",
      "     0     0   35.32909    0   13   47.00000   35.32909  24.8%     -    0s\n",
      "     0     0   37.00000    0   15   47.00000   37.00000  21.3%     -    0s\n",
      "     0     0   38.42857    0   15   47.00000   38.42857  18.2%     -    0s\n",
      "     0     0   38.42857    0   15   47.00000   38.42857  18.2%     -    0s\n",
      "     0     0   39.00000    0   19   47.00000   39.00000  17.0%     -    0s\n",
      "     0     0   43.00000    0   19   47.00000   43.00000  8.51%     -    0s\n",
      "\n",
      "Cutting planes:\n",
      "  Implied bound: 2\n",
      "  MIR: 21\n",
      "  RLT: 1\n",
      "  Relax-and-lift: 4\n",
      "\n",
      "Explored 1 nodes (281 simplex iterations) in 0.05 seconds (0.02 work units)\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 5: 47 49 54 ... 70\n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 4.700000000000e+01, best bound 4.700000000000e+01, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "model.optimize()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualizing the solution\n",
    "### Retrieving the solution\n",
    "\n",
    "Once the solution has been calculated, we want to validate this by visualizing in several ways. To get started with that, we first retrieve the values for all variables and structure this information in a useful way. For every combination of a train and a resource being visited, we collect the time of reaching that resource, as well as the next resource and the time of reaching that next resource."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "intervals = {\n",
    "    (train, resource): (tvar(train, resource).X, tvar(train, get_next_resource(train, resource)).X, get_next_resource(train, resource) )\n",
    "    for (train, resource) in events\n",
    "}\n",
    "model.dispose()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Displaying the solution per train and per resource"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A quick-and-dirty way to visualize the resulting schedule, is by creating a (pivot) table where the columns represent the resources (the horizontal axis represents *space*) and the rows represent trains. The cells show the time at which the train starts occupying the resource. The direction of travel can be seen easily from the fact that the times of a particular train increase going from left to right, or right to left."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/var/folders/c2/2cvvyd0s4jd_bl77ppy651kh0002ym/T/ipykernel_22752/1260593270.py:4: FutureWarning: Downcasting object dtype arrays on .fillna, .ffill, .bfill is deprecated and will change in a future version. Call result.infer_objects(copy=False) instead. To opt-in to the future behavior, set `pd.set_option('future.no_silent_downcasting', True)`\n",
      "  df_intervals.pivot_table(values='start', columns='resource', index='train', fill_value='')\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th>resource</th>\n",
       "      <th>0</th>\n",
       "      <th>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "      <th>6</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>train</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>A</th>\n",
       "      <td>0.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>12.0</td>\n",
       "      <td>24.0</td>\n",
       "      <td>32.0</td>\n",
       "      <td>34.0</td>\n",
       "      <td>39.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>B</th>\n",
       "      <td></td>\n",
       "      <td>0.0</td>\n",
       "      <td>6.0</td>\n",
       "      <td>16.0</td>\n",
       "      <td>24.0</td>\n",
       "      <td>26.0</td>\n",
       "      <td>31.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>C</th>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "      <td>0.0</td>\n",
       "      <td>8.0</td>\n",
       "      <td>10.0</td>\n",
       "      <td>15.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>D</th>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "      <td>0.0</td>\n",
       "      <td>2.0</td>\n",
       "      <td>7.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>E</th>\n",
       "      <td>26.0</td>\n",
       "      <td>20.0</td>\n",
       "      <td>16.0</td>\n",
       "      <td>8.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>F</th>\n",
       "      <td>50.0</td>\n",
       "      <td>44.0</td>\n",
       "      <td>40.0</td>\n",
       "      <td>32.0</td>\n",
       "      <td>26.0</td>\n",
       "      <td>15.0</td>\n",
       "      <td>0.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "resource     0     1     2     3     4     5     6\n",
       "train                                             \n",
       "A          0.0   6.0  12.0  24.0  32.0  34.0  39.0\n",
       "B                0.0   6.0  16.0  24.0  26.0  31.0\n",
       "C                            0.0   8.0  10.0  15.0\n",
       "D                                  0.0   2.0   7.0\n",
       "E         26.0  20.0  16.0   8.0   0.0            \n",
       "F         50.0  44.0  40.0  32.0  26.0  15.0   0.0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_intervals = pd.DataFrame.from_dict(intervals, orient='index').rename(columns={0:'start',1:'end',2:'next'}).reset_index()\n",
    "df_intervals['train'], df_intervals['resource'] = zip(*df_intervals['index'])\n",
    "df_intervals.drop(columns='index', inplace=True)\n",
    "df_intervals.pivot_table(values='start', columns='resource', index='train', fill_value='')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visualizing the schedule with a time-space diagram"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Train schedules are typically visualized by showing space on the *vertical* axis and time on the *horizontal* axis. Stations have specific points on the y-axis whereas tracks are the space between those stations. Individual train trips are paths through the diagram, connecting (location, time) pairs. Horizontal line segments show that the train stands still at a station. When two trains run in the same direction and their path crosses, it means the faster train takes over the slower train. To construct such visualization, we first need to compute Y coordinates for each event of each train."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# For each train, compute Y coodinates per event\n",
    "train_coordinates = { }\n",
    "for train, route in trains.items():\n",
    "    current_resource = None\n",
    "    for resource in route:\n",
    "        if resource_type[resource] == 'S':\n",
    "            train_coordinates[train, resource] = (station_y[resource], station_y[resource])\n",
    "        else:\n",
    "            endpoints = track_stations[resource]\n",
    "            if current_resource != None:\n",
    "                first = current_resource\n",
    "                second = endpoints[0] if endpoints[1] == current_resource else endpoints[1]                \n",
    "            else:\n",
    "                second = route[1]\n",
    "                first = endpoints[0] if endpoints[1] == second else endpoints[1]\n",
    "            train_coordinates[train, resource] = (station_y[first], station_y[second])\n",
    "        current_resource = resource"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we have those coordinates, we can compute the individual line segments per train and then connect those as paths. We draw the stations as dotted lines. Usually the slope of the line segment represents the speed of the train.\n",
    "\n",
    "Note that for the `yshape` dataset, there is a junction in the track but the two branches cannot be properly visualized in one dimension. Station 6 is drawn between stations 4 and 8, even though trains running from station 4 to 8 don't actually pass by/through station 6."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.plotly.v1+json": {
       "config": {
        "plotlyServerURL": "https://plot.ly"
       },
       "data": [
        {
         "hovertemplate": "train=A<br>x=%{x}<br>y=%{y}<extra></extra>",
         "legendgroup": "A",
         "line": {
          "color": "#636efa",
          "dash": "solid",
          "width": 4
         },
         "marker": {
          "symbol": "circle"
         },
         "mode": "lines",
         "name": "A",
         "opacity": 0.7,
         "orientation": "v",
         "showlegend": true,
         "type": "scatter",
         "x": [
          0,
          6,
          6,
          12,
          12,
          24,
          24,
          32,
          32,
          34,
          34,
          39,
          39,
          41
         ],
         "xaxis": "x",
         "y": [
          0,
          0,
          0,
          6,
          6,
          6,
          6,
          14,
          14,
          14,
          14,
          19,
          19,
          19
         ],
         "yaxis": "y"
        },
        {
         "hovertemplate": "train=B<br>x=%{x}<br>y=%{y}<extra></extra>",
         "legendgroup": "B",
         "line": {
          "color": "#EF553B",
          "dash": "solid",
          "width": 4
         },
         "marker": {
          "symbol": "circle"
         },
         "mode": "lines",
         "name": "B",
         "opacity": 0.7,
         "orientation": "v",
         "showlegend": true,
         "type": "scatter",
         "x": [
          0,
          6,
          6,
          16,
          16,
          24,
          24,
          26,
          26,
          31,
          31,
          33
         ],
         "xaxis": "x",
         "y": [
          0,
          6,
          6,
          6,
          6,
          14,
          14,
          14,
          14,
          19,
          19,
          19
         ],
         "yaxis": "y"
        },
        {
         "hovertemplate": "train=C<br>x=%{x}<br>y=%{y}<extra></extra>",
         "legendgroup": "C",
         "line": {
          "color": "#00cc96",
          "dash": "solid",
          "width": 4
         },
         "marker": {
          "symbol": "circle"
         },
         "mode": "lines",
         "name": "C",
         "opacity": 0.7,
         "orientation": "v",
         "showlegend": true,
         "type": "scatter",
         "x": [
          0,
          8,
          8,
          10,
          10,
          15,
          15,
          17
         ],
         "xaxis": "x",
         "y": [
          6,
          14,
          14,
          14,
          14,
          19,
          19,
          19
         ],
         "yaxis": "y"
        },
        {
         "hovertemplate": "train=D<br>x=%{x}<br>y=%{y}<extra></extra>",
         "legendgroup": "D",
         "line": {
          "color": "#ab63fa",
          "dash": "solid",
          "width": 4
         },
         "marker": {
          "symbol": "circle"
         },
         "mode": "lines",
         "name": "D",
         "opacity": 0.7,
         "orientation": "v",
         "showlegend": true,
         "type": "scatter",
         "x": [
          0,
          2,
          2,
          7,
          7,
          9
         ],
         "xaxis": "x",
         "y": [
          14,
          14,
          14,
          19,
          19,
          19
         ],
         "yaxis": "y"
        },
        {
         "hovertemplate": "train=E<br>x=%{x}<br>y=%{y}<extra></extra>",
         "legendgroup": "E",
         "line": {
          "color": "#FFA15A",
          "dash": "solid",
          "width": 4
         },
         "marker": {
          "symbol": "circle"
         },
         "mode": "lines",
         "name": "E",
         "opacity": 0.7,
         "orientation": "v",
         "showlegend": true,
         "type": "scatter",
         "x": [
          0,
          8,
          8,
          16,
          16,
          20,
          20,
          26,
          26,
          28
         ],
         "xaxis": "x",
         "y": [
          14,
          14,
          14,
          6,
          6,
          6,
          6,
          0,
          0,
          0
         ],
         "yaxis": "y"
        },
        {
         "hovertemplate": "train=F<br>x=%{x}<br>y=%{y}<extra></extra>",
         "legendgroup": "F",
         "line": {
          "color": "#19d3f3",
          "dash": "solid",
          "width": 4
         },
         "marker": {
          "symbol": "circle"
         },
         "mode": "lines",
         "name": "F",
         "opacity": 0.7,
         "orientation": "v",
         "showlegend": true,
         "type": "scatter",
         "x": [
          0,
          15,
          15,
          26,
          26,
          32,
          32,
          40,
          40,
          44,
          44,
          50,
          50,
          52
         ],
         "xaxis": "x",
         "y": [
          19,
          19,
          19,
          14,
          14,
          14,
          14,
          6,
          6,
          6,
          6,
          0,
          0,
          0
         ],
         "yaxis": "y"
        }
       ],
       "layout": {
        "annotations": [
         {
          "showarrow": false,
          "text": "0",
          "x": 1,
          "xanchor": "right",
          "xref": "x domain",
          "y": 0,
          "yanchor": "bottom",
          "yref": "y"
         },
         {
          "showarrow": false,
          "text": "2",
          "x": 1,
          "xanchor": "right",
          "xref": "x domain",
          "y": 6,
          "yanchor": "bottom",
          "yref": "y"
         },
         {
          "showarrow": false,
          "text": "4",
          "x": 1,
          "xanchor": "right",
          "xref": "x domain",
          "y": 14,
          "yanchor": "bottom",
          "yref": "y"
         },
         {
          "showarrow": false,
          "text": "6",
          "x": 1,
          "xanchor": "right",
          "xref": "x domain",
          "y": 19,
          "yanchor": "bottom",
          "yref": "y"
         }
        ],
        "height": 400,
        "legend": {
         "title": {
          "text": "train"
         },
         "tracegroupgap": 0
        },
        "margin": {
         "t": 60
        },
        "shapes": [
         {
          "line": {
           "color": "gray",
           "dash": "dot",
           "width": 1
          },
          "type": "line",
          "x0": 0,
          "x1": 1,
          "xref": "x domain",
          "y0": 0,
          "y1": 0,
          "yref": "y"
         },
         {
          "line": {
           "color": "gray",
           "dash": "dot",
           "width": 1
          },
          "type": "line",
          "x0": 0,
          "x1": 1,
          "xref": "x domain",
          "y0": 6,
          "y1": 6,
          "yref": "y"
         },
         {
          "line": {
           "color": "gray",
           "dash": "dot",
           "width": 1
          },
          "type": "line",
          "x0": 0,
          "x1": 1,
          "xref": "x domain",
          "y0": 14,
          "y1": 14,
          "yref": "y"
         },
         {
          "line": {
           "color": "gray",
           "dash": "dot",
           "width": 1
          },
          "type": "line",
          "x0": 0,
          "x1": 1,
          "xref": "x domain",
          "y0": 19,
          "y1": 19,
          "yref": "y"
         }
        ],
        "template": {
         "data": {
          "bar": [
           {
            "error_x": {
             "color": "#2a3f5f"
            },
            "error_y": {
             "color": "#2a3f5f"
            },
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "bar"
           }
          ],
          "barpolar": [
           {
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "barpolar"
           }
          ],
          "carpet": [
           {
            "aaxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "baxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "type": "carpet"
           }
          ],
          "choropleth": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "choropleth"
           }
          ],
          "contour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "contour"
           }
          ],
          "contourcarpet": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "contourcarpet"
           }
          ],
          "heatmap": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmap"
           }
          ],
          "heatmapgl": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmapgl"
           }
          ],
          "histogram": [
           {
            "marker": {
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "histogram"
           }
          ],
          "histogram2d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2d"
           }
          ],
          "histogram2dcontour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2dcontour"
           }
          ],
          "mesh3d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "mesh3d"
           }
          ],
          "parcoords": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "parcoords"
           }
          ],
          "pie": [
           {
            "automargin": true,
            "type": "pie"
           }
          ],
          "scatter": [
           {
            "fillpattern": {
             "fillmode": "overlay",
             "size": 10,
             "solidity": 0.2
            },
            "type": "scatter"
           }
          ],
          "scatter3d": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatter3d"
           }
          ],
          "scattercarpet": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattercarpet"
           }
          ],
          "scattergeo": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergeo"
           }
          ],
          "scattergl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergl"
           }
          ],
          "scattermapbox": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattermapbox"
           }
          ],
          "scatterpolar": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolar"
           }
          ],
          "scatterpolargl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolargl"
           }
          ],
          "scatterternary": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterternary"
           }
          ],
          "surface": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "surface"
           }
          ],
          "table": [
           {
            "cells": {
             "fill": {
              "color": "#EBF0F8"
             },
             "line": {
              "color": "white"
             }
            },
            "header": {
             "fill": {
              "color": "#C8D4E3"
             },
             "line": {
              "color": "white"
             }
            },
            "type": "table"
           }
          ]
         },
         "layout": {
          "annotationdefaults": {
           "arrowcolor": "#2a3f5f",
           "arrowhead": 0,
           "arrowwidth": 1
          },
          "autotypenumbers": "strict",
          "coloraxis": {
           "colorbar": {
            "outlinewidth": 0,
            "ticks": ""
           }
          },
          "colorscale": {
           "diverging": [
            [
             0,
             "#8e0152"
            ],
            [
             0.1,
             "#c51b7d"
            ],
            [
             0.2,
             "#de77ae"
            ],
            [
             0.3,
             "#f1b6da"
            ],
            [
             0.4,
             "#fde0ef"
            ],
            [
             0.5,
             "#f7f7f7"
            ],
            [
             0.6,
             "#e6f5d0"
            ],
            [
             0.7,
             "#b8e186"
            ],
            [
             0.8,
             "#7fbc41"
            ],
            [
             0.9,
             "#4d9221"
            ],
            [
             1,
             "#276419"
            ]
           ],
           "sequential": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ],
           "sequentialminus": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ]
          },
          "colorway": [
           "#636efa",
           "#EF553B",
           "#00cc96",
           "#ab63fa",
           "#FFA15A",
           "#19d3f3",
           "#FF6692",
           "#B6E880",
           "#FF97FF",
           "#FECB52"
          ],
          "font": {
           "color": "#2a3f5f"
          },
          "geo": {
           "bgcolor": "white",
           "lakecolor": "white",
           "landcolor": "#E5ECF6",
           "showlakes": true,
           "showland": true,
           "subunitcolor": "white"
          },
          "hoverlabel": {
           "align": "left"
          },
          "hovermode": "closest",
          "mapbox": {
           "style": "light"
          },
          "paper_bgcolor": "white",
          "plot_bgcolor": "#E5ECF6",
          "polar": {
           "angularaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "radialaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "scene": {
           "xaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "yaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "zaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           }
          },
          "shapedefaults": {
           "line": {
            "color": "#2a3f5f"
           }
          },
          "ternary": {
           "aaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "baxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "caxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "title": {
           "x": 0.05
          },
          "xaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          },
          "yaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          }
         }
        },
        "width": 600,
        "xaxis": {
         "anchor": "y",
         "domain": [
          0,
          1
         ],
         "title": {
          "text": "x"
         }
        },
        "yaxis": {
         "anchor": "x",
         "domain": [
          0,
          1
         ],
         "title": {
          "text": "y"
         }
        }
       }
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "df_diagram = it.chain(*[[{ 'train':train, 'y': train_coordinates[train, resource][0], 'x': start }, { 'train':train, 'y': train_coordinates[train, resource][1], 'x':end }] for (train, resource), (start, end, next) in intervals.items()])\n",
    "fig = px.line(df_diagram, x='x', y='y', color='train', width=600, height=400)\n",
    "fig.update_traces(line={'width': 4}, opacity=.7)\n",
    "for station, y_ab in station_y.items():    \n",
    "    fig.add_hline(y=y_ab, annotation_text=station, line_dash=\"dot\", line_width=1, line_color='gray')\n",
    "fig.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Resource occupation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we can visualize the occupancy of each resource in the form of a Gantt chart. Rows represent resources and the horizontal axis represents time. When two bars for different trains overlap, they occupy the same resource (partially) at the same time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.plotly.v1+json": {
       "config": {
        "plotlyServerURL": "https://plot.ly"
       },
       "data": [
        {
         "alignmentgroup": "True",
         "base": [
          "2024-12-18T00:00:00",
          "2024-12-18T00:06:00",
          "2024-12-18T00:12:00",
          "2024-12-18T00:24:00",
          "2024-12-18T00:32:00",
          "2024-12-18T00:34:00",
          "2024-12-18T00:39:00"
         ],
         "hovertemplate": "train=A<br>start=%{base}<br>end=%{x}<br>resource=%{y}<extra></extra>",
         "legendgroup": "A",
         "marker": {
          "color": "#636efa",
          "opacity": 0.5,
          "pattern": {
           "shape": ""
          }
         },
         "name": "A",
         "offsetgroup": "A",
         "orientation": "h",
         "showlegend": true,
         "textposition": "auto",
         "type": "bar",
         "x": [
          360000,
          360000,
          720000,
          480000,
          120000,
          300000,
          120000
         ],
         "xaxis": "x",
         "y": [
          0,
          1,
          2,
          3,
          4,
          5,
          6
         ],
         "yaxis": "y"
        },
        {
         "alignmentgroup": "True",
         "base": [
          "2024-12-18T00:00:00",
          "2024-12-18T00:06:00",
          "2024-12-18T00:16:00",
          "2024-12-18T00:24:00",
          "2024-12-18T00:26:00",
          "2024-12-18T00:31:00"
         ],
         "hovertemplate": "train=B<br>start=%{base}<br>end=%{x}<br>resource=%{y}<extra></extra>",
         "legendgroup": "B",
         "marker": {
          "color": "#EF553B",
          "opacity": 0.5,
          "pattern": {
           "shape": ""
          }
         },
         "name": "B",
         "offsetgroup": "B",
         "orientation": "h",
         "showlegend": true,
         "textposition": "auto",
         "type": "bar",
         "x": [
          360000,
          600000,
          480000,
          120000,
          300000,
          120000
         ],
         "xaxis": "x",
         "y": [
          1,
          2,
          3,
          4,
          5,
          6
         ],
         "yaxis": "y"
        },
        {
         "alignmentgroup": "True",
         "base": [
          "2024-12-18T00:00:00",
          "2024-12-18T00:08:00",
          "2024-12-18T00:10:00",
          "2024-12-18T00:15:00"
         ],
         "hovertemplate": "train=C<br>start=%{base}<br>end=%{x}<br>resource=%{y}<extra></extra>",
         "legendgroup": "C",
         "marker": {
          "color": "#00cc96",
          "opacity": 0.5,
          "pattern": {
           "shape": ""
          }
         },
         "name": "C",
         "offsetgroup": "C",
         "orientation": "h",
         "showlegend": true,
         "textposition": "auto",
         "type": "bar",
         "x": [
          480000,
          120000,
          300000,
          120000
         ],
         "xaxis": "x",
         "y": [
          3,
          4,
          5,
          6
         ],
         "yaxis": "y"
        },
        {
         "alignmentgroup": "True",
         "base": [
          "2024-12-18T00:00:00",
          "2024-12-18T00:02:00",
          "2024-12-18T00:07:00"
         ],
         "hovertemplate": "train=D<br>start=%{base}<br>end=%{x}<br>resource=%{y}<extra></extra>",
         "legendgroup": "D",
         "marker": {
          "color": "#ab63fa",
          "opacity": 0.5,
          "pattern": {
           "shape": ""
          }
         },
         "name": "D",
         "offsetgroup": "D",
         "orientation": "h",
         "showlegend": true,
         "textposition": "auto",
         "type": "bar",
         "x": [
          120000,
          300000,
          120000
         ],
         "xaxis": "x",
         "y": [
          4,
          5,
          6
         ],
         "yaxis": "y"
        },
        {
         "alignmentgroup": "True",
         "base": [
          "2024-12-18T00:00:00",
          "2024-12-18T00:08:00",
          "2024-12-18T00:16:00",
          "2024-12-18T00:20:00",
          "2024-12-18T00:26:00"
         ],
         "hovertemplate": "train=E<br>start=%{base}<br>end=%{x}<br>resource=%{y}<extra></extra>",
         "legendgroup": "E",
         "marker": {
          "color": "#FFA15A",
          "opacity": 0.5,
          "pattern": {
           "shape": ""
          }
         },
         "name": "E",
         "offsetgroup": "E",
         "orientation": "h",
         "showlegend": true,
         "textposition": "auto",
         "type": "bar",
         "x": [
          480000,
          480000,
          240000,
          360000,
          120000
         ],
         "xaxis": "x",
         "y": [
          4,
          3,
          2,
          1,
          0
         ],
         "yaxis": "y"
        },
        {
         "alignmentgroup": "True",
         "base": [
          "2024-12-18T00:00:00",
          "2024-12-18T00:15:00",
          "2024-12-18T00:26:00",
          "2024-12-18T00:32:00",
          "2024-12-18T00:40:00",
          "2024-12-18T00:44:00",
          "2024-12-18T00:50:00"
         ],
         "hovertemplate": "train=F<br>start=%{base}<br>end=%{x}<br>resource=%{y}<extra></extra>",
         "legendgroup": "F",
         "marker": {
          "color": "#19d3f3",
          "opacity": 0.5,
          "pattern": {
           "shape": ""
          }
         },
         "name": "F",
         "offsetgroup": "F",
         "orientation": "h",
         "showlegend": true,
         "textposition": "auto",
         "type": "bar",
         "x": [
          900000,
          660000,
          360000,
          480000,
          240000,
          360000,
          120000
         ],
         "xaxis": "x",
         "y": [
          6,
          5,
          4,
          3,
          2,
          1,
          0
         ],
         "yaxis": "y"
        }
       ],
       "layout": {
        "barmode": "overlay",
        "height": 400,
        "legend": {
         "title": {
          "text": "train"
         },
         "tracegroupgap": 0
        },
        "margin": {
         "t": 60
        },
        "template": {
         "data": {
          "bar": [
           {
            "error_x": {
             "color": "#2a3f5f"
            },
            "error_y": {
             "color": "#2a3f5f"
            },
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "bar"
           }
          ],
          "barpolar": [
           {
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "barpolar"
           }
          ],
          "carpet": [
           {
            "aaxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "baxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "type": "carpet"
           }
          ],
          "choropleth": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "choropleth"
           }
          ],
          "contour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "contour"
           }
          ],
          "contourcarpet": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "contourcarpet"
           }
          ],
          "heatmap": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmap"
           }
          ],
          "heatmapgl": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmapgl"
           }
          ],
          "histogram": [
           {
            "marker": {
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "histogram"
           }
          ],
          "histogram2d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2d"
           }
          ],
          "histogram2dcontour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2dcontour"
           }
          ],
          "mesh3d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "mesh3d"
           }
          ],
          "parcoords": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "parcoords"
           }
          ],
          "pie": [
           {
            "automargin": true,
            "type": "pie"
           }
          ],
          "scatter": [
           {
            "fillpattern": {
             "fillmode": "overlay",
             "size": 10,
             "solidity": 0.2
            },
            "type": "scatter"
           }
          ],
          "scatter3d": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatter3d"
           }
          ],
          "scattercarpet": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattercarpet"
           }
          ],
          "scattergeo": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergeo"
           }
          ],
          "scattergl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergl"
           }
          ],
          "scattermapbox": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattermapbox"
           }
          ],
          "scatterpolar": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolar"
           }
          ],
          "scatterpolargl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolargl"
           }
          ],
          "scatterternary": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterternary"
           }
          ],
          "surface": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "surface"
           }
          ],
          "table": [
           {
            "cells": {
             "fill": {
              "color": "#EBF0F8"
             },
             "line": {
              "color": "white"
             }
            },
            "header": {
             "fill": {
              "color": "#C8D4E3"
             },
             "line": {
              "color": "white"
             }
            },
            "type": "table"
           }
          ]
         },
         "layout": {
          "annotationdefaults": {
           "arrowcolor": "#2a3f5f",
           "arrowhead": 0,
           "arrowwidth": 1
          },
          "autotypenumbers": "strict",
          "coloraxis": {
           "colorbar": {
            "outlinewidth": 0,
            "ticks": ""
           }
          },
          "colorscale": {
           "diverging": [
            [
             0,
             "#8e0152"
            ],
            [
             0.1,
             "#c51b7d"
            ],
            [
             0.2,
             "#de77ae"
            ],
            [
             0.3,
             "#f1b6da"
            ],
            [
             0.4,
             "#fde0ef"
            ],
            [
             0.5,
             "#f7f7f7"
            ],
            [
             0.6,
             "#e6f5d0"
            ],
            [
             0.7,
             "#b8e186"
            ],
            [
             0.8,
             "#7fbc41"
            ],
            [
             0.9,
             "#4d9221"
            ],
            [
             1,
             "#276419"
            ]
           ],
           "sequential": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ],
           "sequentialminus": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ]
          },
          "colorway": [
           "#636efa",
           "#EF553B",
           "#00cc96",
           "#ab63fa",
           "#FFA15A",
           "#19d3f3",
           "#FF6692",
           "#B6E880",
           "#FF97FF",
           "#FECB52"
          ],
          "font": {
           "color": "#2a3f5f"
          },
          "geo": {
           "bgcolor": "white",
           "lakecolor": "white",
           "landcolor": "#E5ECF6",
           "showlakes": true,
           "showland": true,
           "subunitcolor": "white"
          },
          "hoverlabel": {
           "align": "left"
          },
          "hovermode": "closest",
          "mapbox": {
           "style": "light"
          },
          "paper_bgcolor": "white",
          "plot_bgcolor": "#E5ECF6",
          "polar": {
           "angularaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "radialaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "scene": {
           "xaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "yaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "zaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           }
          },
          "shapedefaults": {
           "line": {
            "color": "#2a3f5f"
           }
          },
          "ternary": {
           "aaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "baxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "caxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "title": {
           "x": 0.05
          },
          "xaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          },
          "yaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          }
         }
        },
        "xaxis": {
         "anchor": "y",
         "domain": [
          0,
          1
         ],
         "type": "date"
        },
        "yaxis": {
         "anchor": "x",
         "categoryarray": [
          0,
          1,
          2,
          3,
          4,
          5,
          6
         ],
         "categoryorder": "array",
         "domain": [
          0,
          1
         ],
         "showticklabels": true,
         "title": {
          "text": "resource"
         },
         "type": "category"
        }
       }
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "t = dt.datetime.combine(dt.date.today(), dt.time())\n",
    "df_timeline =  pd.DataFrame.from_records([{ 'train':train, 'resource':resource, 'start':t+dt.timedelta(minutes=start), 'end':t+dt.timedelta(minutes=end) } for (train, resource), (start, end, next) in intervals.items()])\n",
    "fig = px.timeline(df_timeline, x_start='start', x_end='end', y='resource', color='train', height=400, opacity=0.5)\n",
    "fig.update_yaxes(type='category', showticklabels=True, categoryorder='array', categoryarray=sorted(int(x) for x in resources))\n",
    "fig.show() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " # Conclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook we have looked at scheduling for railway operators. We have formulated the scheduling problem as a MIP which can be solved to optimality in reasonable amounts of time using Gurobi for relatively small instances. Of course with the chosen approach, the model size will grow quickly as the number of trains and resources, as well as the capacity of individual resources, increases. More advanced techniques have been developed for solving larger instances. Learn more about these in our [2024 webinar with Sintef](https://www.gurobi.com/events/sintef-railway-optimization/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
